//
//  Problem257.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/6/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 257. 二叉树的所有路径
 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 说明: 叶子节点是指没有子节点的节点。
 示例:
 输入:
    1
  /   \
 2     3
  \
   5

 输出: ["1->2->5", "1->3"]
 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 */
@objcMembers class Problem257: NSObject {
    func solution() {
        let root = TreeNode(1)
        root.left = TreeNode(2)
        root.left?.right = TreeNode(5)
        root.right = TreeNode(3)
        
        print(binaryTreePaths(root))
    }
    
    /*
     DFS 深度优先搜索
     1: 返回左子树的所有路径 leftList
     2: 返回右子树的所有路径 rightList
     3: root+leftList  root+rightList
     */
    func binaryTreePaths(_ root: TreeNode?) -> [String] {
        var list:[String] = []
        if root == nil {
            return []
        } else if root?.left == nil, root?.right == nil {
            return [String(root!.val)]
        }
        
        let leftList = binaryTreePaths(root?.left)
        for path in leftList {
            list.append(String(root!.val) + "->" + path)
        }
        let rightList = binaryTreePaths(root?.right)
        for path in rightList {
            list.append(String(root!.val) + "->" + path)
        }
        return list
    }
}
